#include <stdio.h>
#include <stdlib.h>
//#include "mpi.h"

int weight(int xCoord[], int yCoord[], int i, int j)
{
	return abs(xCoord[i]-xCoord[j]) + abs(yCoord[i]-yCoord[j]);
}

int getPathWeight(int* currPath,int xCoord[], int yCoord[],int nCites)
{
	int i, currPathWeght = 0;
	for (i=0; i<nCites-1; i++)
		currPathWeght += weight(xCoord, yCoord, currPath[i], currPath[i+1]);

	return currPathWeght;
}

int factorial(int n)
{
    if (n <= 1)
        return 1;
    else
        return  n * factorial(n-1);
}

void getPath(int n, int k,int arr[])
{
	int factoradic[n],j,i,data[n],temp[n];
	for (j = 1; j <= n; ++j) {
		factoradic[n-j] = k % j;
		k /= j;
	}
	for (i = 0; i < n; ++i) {
		temp[i] = ++factoradic[i];
	}
	data[n-1] = 1;
	for (i = n-2; i >= 0; --i) {
		data[i] = temp[i];
		for (j = i+1; j < n; ++j) {
			if (data[j] >= data[i])
				++data[j];
		}
	}

	for (i = 0; i < n; ++i)
		--data[i];

	for (j = 0; j < n; ++j)
		arr[j] = data[j];
}

typedef struct DataBuffer {
	int x;
	int y;
	int citiesNum;
} Data;

int tsp_main(int citiesNum, int xCoord[], int yCoord[], int shortestPath[])
{
	MPI_Datatype buffType;
	MPI_Type_contiguous(3,MPI_INT,&buffType);
	MPI_Type_commit(&buffType);
	int rank,prosesorsNum,i;
	MPI_Status status;
	MPI_Request request;
	MPI_Comm comm;
	MPI_Comm_rank (MPI_COMM_WORLD, &rank);
	MPI_Comm_size (MPI_COMM_WORLD, &prosesorsNum);
	if (citiesNum <= 0)
		  return 0;

	Data* coordinates = malloc(sizeof(Data)*citiesNum);
	if (coordinates == NULL)
		exit(0);

	if (rank == 0) {
		for (i = 0; i < citiesNum; i++) {
			coordinates[i].x = xCoord[i];
			coordinates[i].y = yCoord[i];
			coordinates[i].citiesNum = citiesNum;
		}
	}

	MPI_Barrier(MPI_COMM_WORLD);
	MPI_Bcast(coordinates, citiesNum, buffType, 0, MPI_COMM_WORLD);
	MPI_Barrier(MPI_COMM_WORLD);

	int min = ~0*(-1), currPathWeight = 0, cities = coordinates[0].citiesNum;
	int* x = malloc(sizeof(int)*cities);
	if (x == NULL) {
		free(coordinates);
		exit(0);
	}

	int* y = malloc(sizeof(int)*cities);
	if(y == NULL){
		free(coordinates);
		free(x);
		exit(0);
	}

	for (i=0; i < cities; i++) {
		for (i = 0; i < cities; i++) {
			x[i] = coordinates[i].x;
			y[i] = coordinates[i].y;
		}
	}

	int* currPath = malloc(sizeof(int)*cities);
	if (currPath == NULL) {
		free(coordinates);
		free(x);
		free(y);
		exit(0);
	}

	int fromPath,toPath,currPathWeght;
	int chunk = factorial(citiesNum)/prosesorsNum;
	if (factorial(citiesNum)<prosesorsNum) {
		fromPath = rank;
		toPath = rank;
	} else {
		fromPath = rank*chunk;
		toPath = (rank == (prosesorsNum-1)) ? factorial(citiesNum)-1 : fromPath + chunk;
	}

	if (!(factorial(citiesNum)<prosesorsNum && rank>factorial(citiesNum))) {
		min = ~0*(-1);
	} else {
		for (i = fromPath; i < toPath; i++) {
			getPath(cities,i,currPath);
			currPathWeght = getPathWeight(currPath,x,y,cities);
			if(currPathWeght < min)
				min = currPathWeght;
		}
	}

	if (rank == 0) {
		int recvMin;
		while (prosesorsNum > 1) {
			MPI_Recv(&recvMin, 1,MPI_INT, MPI_ANY_SOURCE,MPI_ANY_TAG , MPI_COMM_WORLD, &status);
			if(recvMin < min ){
				min = recvMin;
			}
			prosesorsNum--;
		}
	} else {
		MPI_Isend(&min,1, MPI_INT,0,MPI_ANY_TAG , MPI_COMM_WORLD, &request);
	}

	free(coordinates);
	free(x);
	free(y);
	return min;
}

